#include<vector>
#include<functional>
using namespace std;
class Solution {
public:
    //环形dp分离成两个线性dp
    int rob(vector<int>& nums) {
        if(nums.size()==1)return nums.back();
        function<int(int,int)>__rob=[&](int begin,int end)->int{            
            vector<vector<int>>dp(end,vector<int>(2,0));
            dp[begin][0]=0,dp[begin][1]=nums[begin];
            for(int i=begin+1;i<end;i++){
                dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
                dp[i][1]=dp[i-1][0]+nums[i];
            }
            return max(dp.back()[0],dp.back()[1]);
        };
        return max(__rob(0,nums.size()-1),__rob(1,nums.size()));
    }
};